//峰值元素是指其值严格大于左右相邻值的元素。 
//
// 给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。 
//
// 你可以假设 nums[-1] = nums[n] = -∞ 。 
//
// 你必须实现时间复杂度为 O(log n) 的算法来解决此问题。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,2,3,1]
//输出：2
//解释：3 是峰值元素，你的函数应该返回其索引 2。 
//
// 示例 2： 
//
// 
//输入：nums = [1,2,1,3,5,6,4]
//输出：1 或 5 
//解释：你的函数可以返回索引 1，其峰值元素为 2；
//     或者返回索引 5， 其峰值元素为 6。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 1000 
// -2³¹ <= nums[i] <= 2³¹ - 1 
// 对于所有有效的 i 都有 nums[i] != nums[i + 1] 
// 
//
// Related Topics 数组 二分查找 👍 1056 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

class Solution162
{
    // 往高处走
    public int findPeakElement(int[] nums) {
        int l = 0, r = nums.length - 1;

        while (l <= r) {
            int mid = l + (r - l) / 2;
            // 1. 就是答案, 返回
            // 2. 比某一侧小, 取那一侧
            if (compare(nums, mid, mid + 1) > 0 && compare(nums, mid, mid - 1) > 0) {
                return mid;
            }
            if (compare(nums, mid, mid - 1) < 0) {
                r = mid - 1;
            } else if (compare(nums, mid, mid + 1) < 0) {
                l = mid + 1;
            }
        }

        return -1;
    }

    // 简化越界处理
    int compare(int[] nums, int i, int j) {
        boolean iout = i < 0 || i >= nums.length;
        boolean jout = j < 0 || j >= nums.length;
        long ival = iout ? Long.MIN_VALUE : nums[i];
        long jval = jout ? Long.MIN_VALUE : nums[j];
        return ival == jval ? 0 : (ival < jval ? -1 : 1);
    }

    int compare_1(int[] nums, int i, int j) {
        boolean iout = i < 0 || i >= nums.length;
        boolean jout = j < 0 || j >= nums.length;
        if (iout && jout) {
            return 0;
        } else if (iout) {
            return -1;
        } else if (jout) {
            return 1;
        }

        return nums[i] == nums[j] ? 0 : (nums[i] < nums[j] ? -1 : 1);
    }
}


// Fail, [1,6,5,4,3,2,1]
class Solution162_Fail {
    // 1, 2, 1, 3, 5, 6, 4
    public int findPeakElement(int[] nums) {
        int l = 0, r = nums.length - 1;
        int mid = l + (r - l) / 2;
        int currMaxIx = mid;
        while (l <= r) {
            int tmp = 0;
            // 左中右取最大
            if (nums[l] > nums[r]) {
                tmp = nums[l] > nums[mid] ? l : mid;
                r = mid - 1;
            } else {
                tmp = nums[r] > nums[mid] ? r : mid;
                l = mid + 1;
            }

            if (nums[tmp] > nums[currMaxIx]) {
                currMaxIx = tmp;
            }

            mid = l + (r - l) / 2;
        }

        return currMaxIx;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

class Test162 {
    public static void main(String[] args) {
        // int[] nums = {1, 2, 1, 3, 5, 6, 4};
        int[] nums = {-1,2,3,1};
        // int res = new Solution().findPeakElement(nums);
        // System.out.println(res);
    }
}